We study the Maximum Independent Set of Rectangles (MISR) problem: given aset of $n$ axis-parallel rectangles, find a largest-cardinality subset of therectangles, such that no two of them overlap. MISR is a basic geometricoptimization problem with many applications, that has been studied extensively.Until recently, the best approximation algorithm for it achieved an $O(\log\log n)$-approximation factor. In a recent breakthrough, Adamaszek and Wieseprovided a quasi-polynomial time approximation scheme: a$(1-\epsilon)$-approximation algorithm with running time$n^{O(\operatorname{poly}(\log n)/\epsilon)}$. Despite this result, obtaining aPTAS or even a polynomial-time constant-factor approximation remains achallenging open problem. In this paper we make progress towards this goal byproviding an algorithm for MISR that achieves a $(1 - \epsilon)$-approximationin time $n^{O(\operatorname{poly}(\log\log{n} / \epsilon))}$. We introduceseveral new technical ideas, that we hope will lead to further progress on thisand related problems.
展开▼
